A compact disc is submitted with this application that contains an appendix of computer program listings; the contents of the compact disc are hereby incorporated by reference. The disc was created on Apr. 16, 2004 and includes a file entitled xe2x80x9cAppendix.txtxe2x80x9d having a size of 18 KB bytes. A duplicate disc is also submitted.
I. Field of the Invention
The present invention generally relates to the fields of computer graphics and virtual reality. More particularly, the present invention relates to systems and methods for simulating frames of complex virtual environments, including complex virtual environments based on massive models.
II. Background Information
As a result of the advances in computer graphics and computer-aided design (CAD), a wide variety of objects and environments can be modeled and rendered with technical detail and precision. For example, 2D and 3D modeling techniques permit engineering models of mechanical parts and other physical objects to be computer generated for various purposes, such as research and development. In addition, complex environments involving offshore platforms, industrial plants, building complexes and other facilities can be modeled using conventional, computer-aided modeling methods. 3D models of such environments are often used in the architecture, engineering and construction (AEC) sectors and for plant design.
Elements or objects in a complex environment may be represented in a 3D model through polygons. Polygons (such as triangles and quadrilaterals) are closed figures made by joining line segments, wherein each line segment intersects exactly two other line segments. In a 3D model, polygons may be combined to represent the surface(s) of boxes, stairs, windows, walls, floors, pipes, beams and other objects in the modeled environment. Data defining the attributes of each object, including lighting and texture, may also be included in a 3D model.
To render 3D models, conventional graphics systems may be employed. Such graphics systems may be provided with graphics cards that are capable of processing 3D model data to generate and display the modeled environment. While triangle elements can be directly handled and rendered by most graphics cards, other polygon elements in a 3D model (such as four or five-sided polygons) require additional processing before they can be rendered. Such processing may include the triangulation of complex polygon elements into triangles so that it can be directly handled by the graphics hardware and rendered on a display terminal.
With the developments in computer-aided graphics and 3D modeling, there has been an increasing demand for interactive displays and simulation to provide virtual reality. The term virtual reality refers to the use of computer-based simulation of real or imaginary environments that permit a user to perform operations within the simulated environment. In the area of 3D game technology, virtual reality software has been created to provide real-time animation within simulated environments for users. To achieve higher levels of realism, many 3D software games permit users to navigate and/or perform operations (such as lifting, walking, running, jumping, climbing, etc.) in a manner that resembles the real world. For this purpose, the effects of gravity and/or other real-world phenomena (such as collisions) may be simulated in virtual reality applications for 3D game users.
Presently, the ability to provide interactive displays and real-time simulation for complex environments presents many challenges. For example, complex environments can be based on 3D models that are comprised of data representing hundreds of thousands of polygons. Although the throughput of graphics systems has improved over the years, rendering complex environments at interactive frame rates (such as 5 frames/second or higher) is impossible with current applications due to the volume of data that must be processed. For instance, attempts to render complex environments represented by approximately 700,000 or more polygons with current systems will typically cause the screen to freeze or lock when a user tries to navigate through the rendered model.
To overcome such obstacles, some applications eliminate real-world phenomena (such as the effect of gravity and/or collisions) to provide simple navigation features in a complex virtual environment. In such applications, however, the user is often left in a confused state since the user is permitted to navigate through walls, floors and other objects represented in the modeled environment. Further, in some cases, the viewpoint of the user may be positioned within walls or between floors, making it difficult for the user to orientate himself/herself with respect to the rendered frame.
Other applications attempt to provide real-time simulation by reducing the level of detail in the rendered frame and/or eliminating the range of interactive options available to a user. In such applications, however, curved surfaces may appear jagged as opposed to smooth. Further, the user may be limited to basic movements (such as forward, left, right, etc.) that are not practical for most applications. Therefore, while such approaches may improve the frame rate, they fail to provide an acceptable level of visualization and simulation to the user. As a result, past attempts do not provide an effective virtual reality solution for complex environments.
In accordance with embodiments of the invention, a method is provided for performing simulation to facilitate the rendering of frames of a complex virtual environment. Te method comprises: detecting, for a next frame to be rendered, input from a user; determining, based on the user input, desired movements from a current position to a desired position within the complex virtual environment; and performing, using a collision detection hierarchy of bounding boxes that contain one or more elements of the complex environment, a predictive collision detection operation to determine if a collision will occur with an element represented in the complex environment if the desired movements are performed between the current position and the desired position. If a collision is detected, an adjusted position may be calculated based on the desired movements in the complex environment and a viewer position for rendering the next frame may be set to the adjusted position. Further, if a collision is not detected, a viewer position for rendering the next frame may be set to the desired position.
According to other embodiments of the invention, a method is provided for performing simulation operations. The simulation operations being performed as part of a simulation loop to provide interactive displays of the complex environment to a user. Further, the method may comprise: detecting, for a next frame to be rendered, input from a user; determining, based on the user input, desired movements from a current position to a desired position within the complex virtual environment; predicting, using a collision detection hierarchy of bounding boxes that contain one or more elements of the complex environment, whether a collision will occur with an element in the complex environment based on the desired movements between the current position and the desired position; and calculating an adjusted position for rendering the next frame in response to the detection of a collision.
In order to determine desired movements based on the user input, methods consistent with embodiments of the invention may calculate a path between the current position and the desired position based on the user input. Moreover, to predict whether a collision will occur, methods of the invention may perform a proximity query based on the calculated path between the current position and the desired position to identify intersecting bounding boxes, and analyze elements contained in each identified bounding box to determine if a collision will occur based on the desired movements.
Consistent with still additional embodiments of the invention, a computer program product is provided for generating interactive displays of a complex virtual environment. The computer program product may comprise a computer readable medium embodying a computer program, wherein the computer program includes instructions that are executable by a system to perform a simulation method to facilitate the rendering of frames of the complex environment. Such a method may include: determining, based on user input for a frame to be rendered, desired movements from a current position to a desired position within the complex virtual environment; performing, using a collision detection hierarchy of bounding boxes that contain one or more elements of the complex environment, a predictive collision detection operation to determine if a collision will occur with an element represented in the complex environment if the desired movements are performed between the current position and the desired position; and in response to performing the collision detection operation, setting a viewer position for the frame to be rendered.
In accordance with other embodiment of the invention, systems may be provided for generating interactive displays of a complex virtual environment. In such systems, a simulation component may be provided for performing simulations based on virtual reality (VR) file(s). The VR file(s) may include data defining a collision detection hierarchy of bounding boxes that contain elements represented in the complex environment. Further, consistent with embodiments of the invention, the simulation component may comprise: means for determining, based on input from a user, desired movements from a current position to a desired position within the complex virtual environment; means for detecting, using the collision detection hierarchy of bounding boxes, whether a collision will occur with an element represented in the complex virtual environment based on the desired movements from the current position to the desired position; and means for calculating an adjusted position when it is determined that a collision will occur based on the desired movements indicated by the user input.
Other embodiments of the invention may provided, such as a method for simulating movement of an avatar in a complex virtual environment. Such methods may comprise: determining, based on input from a user, desired movements of the avatar from a current position to a desired position within the complex virtual environment; and detecting, using a collision detection hierarchy of bounding boxes, whether a collision will occur with an element represented in the complex virtual environment if the avatar is moved from the current position to the desired position.
To detect collisions, method consistent with embodiments of the invention may perform a proximity query based on the desired movements of the avatar to identify bounding boxes that intersect with the avatar when the avatar is moved to the desired position. Such methods may also analyze elements contained in each identified bounding box to determine if a collision will occur with the avatar.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only, and should not be deemed restrictive of the full scope of the embodiments of the invention.